package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-20 21:00
 **/
public class LeetCode28 {

    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        if (n == 0) {
            return 0;
        }
        int[] next = getNext(needle);
        for (int i = 0, j = 0; i < m; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j- 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == n) {
                return i - n + 1;
            }
        }
        return -1;
    }

    private int[] getNext(String pattern) {
        int len = pattern.length();
        int[] next = new int[len];
        for (int i = 0, j = 1; j < len;j++) {
            while (i > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                i = next[i-1];
            }
            if (pattern.charAt(j) == pattern.charAt(i)) {
                i++;
            }
            next[j] = i;
        }
        return next;
    }

    public static void main(String[] args) {
        LeetCode28 code = new LeetCode28();
        //code.strStr("mississippi", "issip");
        System.out.println(code.strStr("aaaaa", "bba"));
    }

}
